Максимальная оценка за эту задачу — 60 баллов, на проверку необходимо сдавать программу, решающую задачу

В клетки таблицы $n \times n$ необходимо расставить числа от 1 до $n^2$ , каждое по одному разу. Расстановка тем лучше, чем меньше в ней плохих пар соседних клеток. Соседними считаются клетки, имеющие общую сторону. Пара соседних клеток считается плохой, если числа в этих клетках не являются взаимно простыми. Два числа называются взаимно простыми, если их наибольший общий делитель равен $1$ .

Составьте таблицу с наименьшим количеством плохих пар клеток.

Формат ввода

В первой строке задается количество наборов входных данных $T$ . В этой задаче $T$ всегда равно 1.

В следующих $T$ строках содержатся описания входных данных. Каждое описание состоит из одного целого числа $n$ $(2 \le n \le 100)$ — размера таблицы.

Формат вывода

Для каждого набора входных данных выведите $n$ строк, в каждой из которых должно быть по $n$ целых чисел — выбранная таблица.

Все числа от $1$ до $n^2$ должны встретиться в таблице ровно один раз.

Система оценивания

Оценка за эту задачу — 60 баллов.

В этой задаче 60 тестов, и каждый тест оценивается максимум в 1 балл. Оценка за тест вычисляется как средняя оценка по наборам входных данных в тесте. В этой задаче оценка за тест равна оценке за единственный набор входных данных соответственно. Оценка за набор входных данных вычисляется по формуле:

$grade = 1 - 1.7\cdot \frac{bad}{n^2}$

где $bad$ и $n$ — количество плохих пар и размер таблицы соответственно.

Пример

Ввод	Вывод
1 2	1 4 2 3

Ограничение времени	2 секунды
Ограничение памяти	256 Мб
Ввод	стандартный ввод или input.txt
Вывод	стандартный вывод или output.txt

Взаимнопростая таблица - 1

Формат ввода

Формат вывода

Система оценивания

Пример